package pers.qianyu.month_202101.date_20210131;

/**
 * 第 226 场周赛 第 4 题
 * 5666. 回文串分割 IV
 * https://leetcode-cn.com/problems/palindrome-partitioning-iv/
 *
 * @author mizzle rain
 * @date 2021-01-31 15:55
 */
public class CheckPartitioning {
    public boolean checkPartitioning(String s) {
        int len = s.length();
        if (len == 0) return false;
        char[] arr = s.toCharArray();
        boolean[][] dp = new boolean[len][len];
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j) dp[i][j] = true;
                else if (i + 1 == j) dp[i][j] = arr[i] == arr[j];
                else dp[i][j] = arr[i] == arr[j] && dp[i + 1][j - 1];
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][len - 1]) return true;
            }
        }
        return false;
    }
}
